#define _CRT_SECURE_NO_WARNINGS 1
#include <queue>
#include <set>
using namespace std;
int x[] = { 2,3,5 };
class Solution {
public:
    int nthUglyNumber(int n)
    {
        priority_queue<long long, vector<long long>, greater<long long>> pq;
        set<long long> s;
        pq.push(1);
        s.insert(1);
        for (int i = 1;i < n;i++)
        {
            auto top = pq.top();
            pq.pop();
            for (int i = 0;i < 3;i++)
            {
                if (s.find(top * x[i]) == s.end())
                {
                    s.insert(top * x[i]);
                    pq.push(top * x[i]);
                }
            }
        }
        return pq.top();
    }
};